package site.wanjiahao.union;

/**
 * Quick Union
 * find O(logn)
 * Union O(logn)
 *
 * 路径分裂
 */
public class UnionFind_QU_R_PS extends UnionFind_QU_R {


    public UnionFind_QU_R_PS(int capacity) {
        super(capacity);
    }

    // 路径分裂，使路径上的节点指向其祖父节点
    @Override
    public int find(int v) {
        checkRange(v);
        while (v != parents[v]) {
            int parent = parents[v];
            parents[v] = parents[parent];
            v = parent;
        }
        return v;
    }
}
